#include "fast_crc.h"
#include "base/thread_util.h"

static uint32 crc_table[4][256];
static uint32 crc_combine_table[32][4][256];
static bool crc_initialized = false;
static Mutex crc_mutex;

uint32 crc32(uint32 crc, const uint8* block, uint32 leng) {
  const uint32 *block4;

#define CRC_REORDER crc^=0xFFFFFFFF
#define CRC_ONE_BYTE crc = crc_table[0][(crc ^ *block++) & 0xFF] ^ (crc >> 8)
#define CRC_FOUR_BYTES crc ^= *block4++; crc = crc_table[3][crc & 0xff] ^ crc_table[2][(crc >> 8) & 0xff] ^ crc_table[1][(crc >> 16) & 0xff] ^ crc_table[0][crc >> 24]

  CRC_REORDER;
  while (leng && ((unsigned long) block & 3)) {
    CRC_ONE_BYTE;
    leng--;
  }
  block4 = (const uint32*) block;
  while (leng >= 32) {
    CRC_FOUR_BYTES
    ;
    CRC_FOUR_BYTES
    ;
    CRC_FOUR_BYTES
    ;
    CRC_FOUR_BYTES
    ;
    CRC_FOUR_BYTES
    ;
    CRC_FOUR_BYTES
    ;
    CRC_FOUR_BYTES
    ;
    CRC_FOUR_BYTES
    ;
    leng -= 32;
  }
  while (leng >= 4) {
    CRC_FOUR_BYTES
    ;
    leng -= 4;
  }
  block = (const uint8*) block4;
  if (leng) do {
    CRC_ONE_BYTE;
  } while (--leng);
  CRC_REORDER;
  return crc;
}

uint32 crc32_combine(uint32 crc1, uint32 crc2, uint32 leng2) {
  uint8 i;

  /* add leng2 zeros to crc1 */
  i = 0;
  while (leng2) {
    if (leng2 & 1) {
      crc1 = crc_combine_table[i][3][(crc1 >> 24)]
          ^ crc_combine_table[i][2][(crc1 >> 16) & 0xFF]
          ^ crc_combine_table[i][1][(crc1 >> 8) & 0xFF]
          ^ crc_combine_table[i][0][crc1 & 0xFF];
    }
    i++;
    leng2 >>= 1;
  };
  /* then combine crc1 and crc2 as output */
  return crc1 ^ crc2;
}

static void crc_generate_main_tables(void) {
  uint32 c, poly, i;

#define CRC_POLY 0xEDB88320U
  poly = CRC_POLY;
  for (i = 0; i < 256; i++) {
    c = i;
    c = (c & 1) ? (poly ^ (c >> 1)) : (c >> 1);
    c = (c & 1) ? (poly ^ (c >> 1)) : (c >> 1);
    c = (c & 1) ? (poly ^ (c >> 1)) : (c >> 1);
    c = (c & 1) ? (poly ^ (c >> 1)) : (c >> 1);
    c = (c & 1) ? (poly ^ (c >> 1)) : (c >> 1);
    c = (c & 1) ? (poly ^ (c >> 1)) : (c >> 1);
    c = (c & 1) ? (poly ^ (c >> 1)) : (c >> 1);
    c = (c & 1) ? (poly ^ (c >> 1)) : (c >> 1);
    crc_table[0][i] = c;
  }

  for (i = 0; i < 256; i++) {
    c = crc_table[0][i];
    c = crc_table[0][c & 0xff] ^ (c >> 8);
    crc_table[1][i] = c;
    c = crc_table[0][c & 0xff] ^ (c >> 8);
    crc_table[2][i] = c;
    c = crc_table[0][c & 0xff] ^ (c >> 8);
    crc_table[3][i] = c;
  }
}

/* crc_combine */
static void crc_matrix_square(uint32 sqr[32], uint32 m[32]) {
  uint32 i, j, s, v;
  for (i = 0; i < 32; i++) {
    for (j = 0, s = 0, v = m[i]; v && j < 32; j++, v >>= 1) {
      if (v & 1) {
        s ^= m[j];
      }
    }
    sqr[i] = s;
  }
}

static void crc_generate_combine_tables(void) {
  uint32 i, j, k, l, sum;
  uint32 m1[32], m2[32], *mc, *m;
  m1[0] = CRC_POLY;
  j = 1;
  for (i = 1; i < 32; i++) {
    m1[i] = j;
    j <<= 1;
  }
  crc_matrix_square(m2, m1);  // 1 bit -> 2 bits
  crc_matrix_square(m1, m2);  // 2 bits -> 4 bits

  for (i = 0; i < 32; i++) {
    if (i & 1) {
      crc_matrix_square(m1, m2);
      mc = m1;
    } else {
      crc_matrix_square(m2, m1);
      mc = m2;
    }
    for (j = 0; j < 4; j++) {
      for (k = 0; k < 256; k++) {
        sum = 0;
        l = k;
        m = mc + (j * 8);
        while (l) {
          if (l & 1) {
            sum ^= *m;
          }
          l >>= 1;
          m++;
        }
        crc_combine_table[i][j][k] = sum;
      }
    }
  }
}

void crc32_init() {
  ScopedMutex l(&crc_mutex);
  if (crc_initialized) return;

  crc_initialized = true;
  crc_generate_main_tables();
  crc_generate_combine_tables();
}
